A computer system includes a set of interconnected components or modules of three basic types: central processing unit (CPU), data and instruction storage, and input/output (I/O). The modules of the computer system are connected together by communication pathways known as busses. A bus is a shared transmission medium in that plural computer modules can transmit across the same bus. However, if two modules transmit during the same time period, their signals will overlap and become garbled. Therefore, it is important to ensure that only one module transmits across the bus during a given time period.
The process of allocating time or bandwidth on a computer bus among plural bus masters (i.e., modules driving the computer bus) is known as arbitration. Typically, an arbiter grants access for a predetermined time period or bandwidth window to whichever bus master first transaction requests use of the bus. If plural bus masters have requests for use of the bus pending, then the arbiter employs an arbitration scheme, such as a rotational priority scheme, to share the bus among the bus masters. In a rotational priority scheme, the use of the bus is given for one time period or window to each bus master in sequential order.
In a typical computer system, an expansion bus, such as a Peripheral Component Interconnect (PCI) bus, is coupled by a PCI-host bridge to a processor bus connected to the central processing unit. The bus masters coupled to the PCI bus transmit transaction requests across the PCI bus and the PCI-host bridge to a system memory module via the PCI-host bridge. In many instances, the bus masters issue so many transaction requests to the PCI-host bridge via the PCI bus that the PCI bus becomes saturated. In addition, the resources of the PCI-host bridge may be insufficient to handle the large number of transaction requests being received via the PCI bus. For example, a write buffer in the PCI-host bridge may be full, and thus, unenable to handle another write transaction. If the PCI-host bridge is too busy to process one of the transaction requests, then the PCI-host bridge issues a retry command to the bus master that transmitted the transaction request. The retry command instructs the bus master to re-submit the transaction request because the originally submitted transaction request could not be processed.
Given that the PCI bus is saturated with transaction requests, one of the bus masters may be on the receiving end of such retry commands more than the other bus masters. In particular, the transaction requests may be such that one of the bus masters receives several consecutive retry commands for a single transaction request. This is known as a livelock condition in that transaction requests are continuously being transmitted on the PCI bus, but one of the bus masters is unable to send or receive data.
A simple example of a livelock condition is illustrated in FIG. 1. Bus masters 1 and 4 are requesting read transactions, and bus masters 2 and 3 are requesting write transactions. At the time of the first read transaction request from bus master 1, the write buffer in the PCI-host bridge is empty. The ordering rules for PCI busses require that the write buffer be empty for a read transaction request to be executed, and thus the first read transaction request from bus master 1 is processed normally as indicated by the read transfer status block. The write transaction requests from bus masters 2 and 3 are processed next, which causes the write buffer to go to a "not empty" state. When the PCI-host bridge receives the read transaction request from bus master 4, the PCI-host bridge notices that the write buffer is not empty, and thus the PCI-host bridge is not ready to process the read transaction request. In response, the PCI-host bridge issues a retry command to the bus master 4 via the PCI bus and empties the write buffer.
In response to receiving the retry command from the PCI-host bridge, the bus master 4 arbitrates for access to the PCI bus so that the read transaction request from the bus master 4 can be re-submitted. However, before bus master 4 can gain access to the PCI bus again, bus masters 1, 2, and 3 submit their second transaction requests across the PCI bus to the PCI-host bridge. The transaction requests from the bus masters 2 and 3 are write transaction requests, so the write buffer re-enters the "not empty" state. As a result, the re-submitted read transaction request from bus master 4 cannot be processed, so the PCI-host bridge again issues a retry command to bus master 4 and the sequence begins again. Thus, bus master 4 repeatedly arbitrates for and gains access to the PCI bus, but because of the transaction traffic from the other bus masters, bus master 4 is not in a position to actually complete a transaction, and thus, is in a livelock condition. At some point, the PCI bus traffic likely would change enough to allow bus master 4 to complete its read transaction, but the livelock condition may continue for many milliseconds, which is enough time for latency sensitive devices to generate an error condition.